package com.haidechizi.backup.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: wangdejun
 * @create: 2020-03-14 13:21
 * <p>
 * 线性二叉树，采用数组进行存储
 * 第n个节点的左子节点2*n+1
 * 第n个节点的右子节点2*n+2
 * 第n个节点的父节点(n-1)/2
 **/
public class ArrayBinaryTree {

    private int[] data;

    public ArrayBinaryTree(int[] data) {
        this.data = data;
    }

    public void frontShow() {
        if (data != null && data.length > 0) {
            frontShow(0);

        }
    }

    public void frontShow(int index) {
        System.out.println(data[index]);
        // 遍历左子节点
        int left;
        if ((left = 2 * index + 1) < data.length) {
            frontShow(2 * index + 1);
        }
        // 遍历右子节点
        int right;
        if ((right = 2 * index + 2) < data.length) {
            frontShow(2 * index + 2);

        }
    }


    public void midShow() {
        if (data != null && data.length > 0) {
            midShow(0);
        }
    }

    private void midShow(int i) {
        // 遍历左节点
        int left;
        if ((left = 2 * i + 1) < data.length) {
            midShow(left);
        }
        // 遍历自己
        System.out.println(data[i]);
        // 遍历右节点
        int right;
        if ((right = 2 * i + 2) < data.length) {
            midShow(right);
        }
    }

    public void afterShow() {

        afterShow(0);
    }

    private void afterShow(int i) {
        // 遍历左子树
        int left;
        if ((left = 2 * i + 1) < data.length) {
            afterShow(left);
        }
        int right;
        if ((right = 2 * i + 2) < data.length) {
            afterShow(right);
        }
        System.out.println(data[i]);
    }

    public void deepShow() {
        Queue<Integer> queue = new LinkedList<>();
        // 将根节点的下标添加到队列中
        queue.add(0);
        while (!queue.isEmpty()) {
            int index = queue.poll();
            System.out.println(data[index]);
            int left;
            if ((left = 2 * index + 1) < data.length) {
                queue.add(left);
            }
            int right;
            if ((right = 2 * index + 2) < data.length) {
                queue.add(right);
            }
        }
    }

    public int frontSearch(int d) {
        if (data != null && data.length > 0) {
            return frontSearch(0, d);
        }
        return -1;
    }

    public int frontSearch(int i, int d) {
        int target = -1;
        if (data[i] == d) {
            return i;
        }
        int left;
        if ((left = 2 * i + 1) < data.length) {
            target = frontSearch(left, d);
        }
        if (target >= 0) {
            return target;
        }
        int right;
        if ((right = 2 * i + 2) < data.length) {
            target = frontSearch(right, d);
        }

        return target;
    }
}
